package dfs_bfs.test99;

import listbyorder.utils.TreeNode;

/**
 * 恢复二叉搜索树
 * @author code_yc
 * @version 1.0
 * @date 2020/7/11 9:28
 */
public class Solution1 {

    // 找到左子树中最大的节点， 右子树中最小的节点
    // 如果左子树的最大节点小于右子树的最小节点，直接交换，返回
    // 如果左子树的最大节点大于根节点， 交换
    // 如果右子树的最小节点小于根节点， 交换
    public void recoverTree(TreeNode root) {
        if (root == null) return;
        TreeNode leftMax = getMax(root.left);
        TreeNode rightMin = getMin(root.right);
        if (leftMax != null && rightMin != null && leftMax.val > root.val && rightMin.val < root.val) {
            change(leftMax, rightMin);
            return;
        }
        if (leftMax != null && root.val < leftMax.val) {
            change(leftMax, root);
            return;
        }
        if (rightMin != null && root.val > rightMin.val) {
            change(rightMin, root);
            return;
        }
        recoverTree(root.left);
        recoverTree(root.right);
    }

    // 获取当前树中值最大的节点
    private TreeNode getMax(TreeNode root) {
        if (root == null) return null;
        TreeNode left = getMax(root.left);
        TreeNode right = getMax(root.right);
        TreeNode max = root;
        if (left != null && left.val > max.val) {
            max = left;
        }
        if (right != null && right.val > max.val) {
            max = right;
        }
        return max;
    }

    // 获取当前树中值最小的节点
    private TreeNode getMin(TreeNode root) {
        if (root == null) return null;
        TreeNode left = getMin(root.left);
        TreeNode right = getMin(root.right);
        TreeNode min = root;
        if (left != null && left.val < min.val) {
            min = left;
        }
        if (right != null && right.val < min.val) {
            min = right;
        }
        return min;
    }

    // 交换两个节点的值
    private void change(TreeNode left, TreeNode right) {
        int temp = left.val;
        left.val = right.val;
        right.val = temp;
    }
}
